// 设计一个找到数据流中第 k 大元素的类（class）。
// 注意是排序后的第 k 大元素，不是第 k 个不同的元素。

// 请实现 KthLargest 类：
// 1、KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
// 2、int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

class KthLargest {
    private sortedList: number[];// 维护的排序列表
    private readonly topK: number;// 返回的topK索引
    // 构造函数
    constructor(k: number, nums: number[]) {
        this.topK = k;
        this.sortedList = nums.sort((a, b) => a - b);
    }
    // 二分搜索辅助方法
    private binarySearch(target: number): number {
        let left = 0;
        let right = this.sortedList.length;
        // 这里的搜索区间是左闭右开
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (this.sortedList[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    };
    // add方法
    add(val: number): number {
        const insertIndex = this.binarySearch(val);// 找到应该插入的位置
        this.sortedList.splice(insertIndex, 0, val);// 更新排序数组
        const len = this.sortedList.length;
        return this.sortedList[len - this.topK];
    }
}


// 应该算是比较常规的例题，比较容易想到的是使用堆来进行处理
// 但我在这里使用了更简单的处理，基于数组的 splice 方法来进行维护
// 首先需要对初始化的数组进行排序
// 之后每次插入新元素之后，我们都使用二分搜索来找到数组应该插入的位置
// 每次add都可以维护原数组的有序性，之后便可保证 topK 返回的元素正确。